package merisis.silo;

import static merisis.silo.CakedCursorUtil.MAX_LEVEL;

import java.io.IOException;
import java.io.Writer;

/**
 * Dictionary Access Method.
 * 
 * @author Cheng-Gong Lv
 */
public class SequenceSpace {

	private IndexedNode[] levels = new IndexedNode[MAX_LEVEL + 1];
	private byte numOfLevel;
	private byte toplevel;

	public void init() {

	}

	public byte maxlevel() {

		return toplevel;
	}

	public boolean search(CakedCursor begin, CakedCursor end, String key,
			CakedCursor located) {

		if (!begin.hasNext()) {
			return false;
		}
		Object bkey = begin.get();

		if (!end.hasPrev()) {
			return false;
		}
		Object ekey = end.get();

		while (begin.compareTo(end) <= 0) {

			CakedCursor mid = begin.middle(end);
			String val = (String) mid.get();
			// System.out.println(String.format("** %s-%s, mid%s='%s'", begin,
			// end, mid, val));
			if (val == null) {
				mid.nextEntity();
				val = (String) mid.get();
			}

			int cmp = val.compareTo(key);
			if (cmp < 0) {
				begin.locate(mid);
				begin.nextEntity();

			} else if (cmp > 0) {
				end.locate(mid);
				end.prevEntity();

			} else {

				located.locate(mid);
				return true;
			}
		}

		located.locate(begin);

		return false;
	}

	public void append(String entity) {

		CakedCursor location;
		location = openCursorOnBottom();

		boolean r;
		r = search(openCursorOnBottom(), openCursorOnTop(), entity, location);

		if (!r) {
			add(location, entity);
		}
	}

	public void remove() {

	}

	public CakedCursor openCursorOnBottom() {

		return new CakedCursor(this);
	}

	public CakedCursor openCursorOnTop() {

		return new CakedCursor(this, null);
	}

	public CakedCursor openCursor(byte[] pos) {

		return new CakedCursor(this, pos);
	}

	public void add(CakedCursor cur, String newstr) {

		if (cur.isBegin())
			cur.locate(new byte[] { 0 });
		else if (cur.isEnd()) {
			if (cur.hasPrev())
				cur.nextSlot();
		}

		IndexedNode leaf;

		// find the leaf node located by cursor
		leaf = cur.getLeafNodeOfBranch();
		if (leaf == null) {

			leaf = growNewLeafAlongCursor(cur);
		}

		if (leaf.isFull()) { // no free slot in this leaf
			// System.out.println(String.format("sprout: %s ", cur));
			// System.out.println(String.format("[top: %d: %d]", leaf.getTop(),
			// leaf.getSize()));
			sprout(cur);
			// System.out.println(String.format("[top: %d: %d]", leaf.getTop(),
			// leaf.getSize()));

		}

		if (leaf.isFull()) {
			throw new RuntimeException();
		}

		leaf.insert(cur.offset(0), newstr);
	}

	/**
	 * Grows new leaves at the specified phase in path.
	 * 
	 * @param phase
	 * @param cur
	 * @return
	 */
	public IndexedNode growNewLeafAlongCursor(final CakedCursor cur) {

		IndexedNode node;

		byte level = cur.level();
		byte ph = level;
		if (isEmptyLevel(level)) {

			node = IndexedNode.allocate();
			addLevel(level, node);
		} else {
			node = getRootNodeOfLevel(level);
		}

		// locate the terminal node
		for (; ph > 0; ph--) {

			if (node.get(cur.offset(ph)) == null)
				break;
		}

		// append node until it's leaf node
		for (; ph > 0; ph--) {

			IndexedNode nd = IndexedNode.allocate();
			node.put(cur.offset(ph), nd);
			node = nd;
		}

		return node;
	}

	private boolean isEmptyLevel(byte level) {

		return levels[level] == null;
	}

	public IndexedNode getRootNodeOfLevel(byte level) {

		return levels[level];
	}

	private void addLevel(byte level, IndexedNode node) {

		if (levels[level] != null)
			throw new IllegalStateException(
					"This level has already been created, level=" + level);

		levels[level] = node;
		if (level > toplevel)
			toplevel = level;

		numOfLevel++;
	}

	private byte findForkableKnot(CakedCursor cur) {

		final byte level = cur.level();

		byte forkPhase = -1;

		IndexedNode node = cur.getRootNode();
		for (byte i = level; i > 0; i--) {

			if (!node.isFull()) {
				// at least one empty slot
				forkPhase = i;
			}

			node = cur.getDeeperNodeOfBranch(i);
			assert node != null;
		}

		return forkPhase;
	}

	private void sprout(CakedCursor cur) {

		byte forkknot = findForkableKnot(cur);
		if (forkknot != -1) {

			// fork in this level
			fissi(cur, forkknot);
			return;
		}

		final byte level;
		final byte higherlevel;
		level = cur.level();
		higherlevel = (byte) (level + 1);

		if (level == 0) {

			final IndexedNode mother;
			final IndexedNode daughter;
			mother = cur.getRootNode();
			final byte required = (byte) (mother.getTop() + 1);

			checkLevelAndCarry(higherlevel, required);

			daughter = findFreeHeadNodeInSecondHierachy(higherlevel, required);

			split(mother, daughter, cur, (byte) 0);

		} else if (cur.offset(level) == IndexedNode.boundaryTop()) {

			final IndexedNode mother;
			final IndexedNode daughter;
			mother = cur.getDeeperNodeOfBranch(level);

			checkLevelAndCarry(higherlevel, (byte) 1);
			final IndexedNode scndNextLevel;
			scndNextLevel = findFreeHeadNodeInSecondHierachy(higherlevel,
					(byte) 1);

			daughter = IndexedNode.allocate();
			scndNextLevel.insert(0, daughter);

			split(mother, daughter, cur, (byte) (level - 1));

		} else {

			final IndexedNode root = getRootNodeOfLevel(level);
			final IndexedNode second;
			checkLevelAndCarry(higherlevel, (byte) 1);
			second = findFreeHeadNodeInSecondHierachy(higherlevel, (byte) 1);

			second.takeLatterPart(0, root, IndexedNode.boundaryTop());

			fissi(cur, level);
		}
	}

	private void fissi(CakedCursor cur, byte phase) {

		byte offset = cur.offset(phase);

		IndexedNode place = cur.getNodeOfBranch(phase);

		IndexedNode daughter = IndexedNode.allocate();
		// insert the young daughter
		place.insert(offset + 1, daughter);
		IndexedNode mother = (IndexedNode) place.get(offset);
		if (mother.isEmpty())
			return;

		phase--;
		split(mother, daughter, cur, phase);
	}

	private void checkLevelAndCarry(final byte level, byte numRequiredSlots) {

		byte highLevel = level;
		for (;; highLevel++) {

			// check the root node in this level
			final IndexedNode root;
			root = getRootNodeOfLevel(highLevel);
			if (root == null || root.hasEnoughFreeSlot((byte) 1)) {
				break;
			}

			if (highLevel == 0)
				continue;

			// check the second node in this level
			final IndexedNode second;
			second = (IndexedNode) root.getHeadObject();
			if (second == null || second.hasEnoughFreeSlot(numRequiredSlots))
				break;
		}

		if (highLevel > MAX_LEVEL)
			throw new ArrayIndexOutOfBoundsException("max_level: " + MAX_LEVEL);

		while (highLevel > level) {

			IndexedNode prelvl = getRootNodeOfLevel((byte) (highLevel - 1));

			IndexedNode second = findFreeHeadNodeInSecondHierachy(highLevel,
					(byte) 1);

			second.takeLatterPart(0, prelvl, IndexedNode.boundaryTop());

			highLevel--;
		}
	}

	/**
	 * Find the head node with free slots in the second hierachy.
	 */
	private IndexedNode findFreeHeadNodeInSecondHierachy(byte level,
			byte numRequiredSlots) {

		IndexedNode root = getRootNodeOfLevel(level);
		if (root == null) {

			root = IndexedNode.allocate();
			addLevel(level, root);
		}

		IndexedNode second;
		if (root.getHeadObject() == null) {

			second = IndexedNode.allocate();
			root.putHeadObject(second);
		} else {

			second = (IndexedNode) root.getHeadObject();
			if (!second.hasEnoughFreeSlot(numRequiredSlots)) {
				second = IndexedNode.allocate();
				root.insert(0, second);
			}
		}

		return second;
	}

	private void split(IndexedNode mother, IndexedNode daughter,
			CakedCursor cur, byte phase) {

		// To split the branch nodes. The mother branch should keep
		// the splitting line to link up with the child nodes.
		// The daughter branch will build their link on the head
		// of each young daughter node.

		byte offset;
		for (; phase > 0; phase--) {

			offset = cur.offset(phase);

			daughter.putHeadObject(IndexedNode.allocate());
			daughter.takeLatterPart(1, mother, offset + 1);

			mother = (IndexedNode) mother.get(offset);
			daughter = (IndexedNode) daughter.getHeadObject();
		}

		offset = cur.offset(phase);

		// split the leaf node
		daughter.takeLatterPart(0, mother, offset);
	}

	public void printMap(Writer w, CakedCursor cur, int len) {

		while (cur != null) {

			StringBuilder sb = new StringBuilder();

			sb.append(String.format("%02x: ", cur.level()));
			int k = 0;
			for (int i = cur.level(); i >= 0 && k < 10; i--, k++) {
				sb.append(String.format("%02x|", cur.offset(i)));
			}
			for (; k < 10; k++) {
				sb.append("  |");
			}

			sb.append("  ");

			IndexedNode leaf = cur.getLeafNodeOfBranch();

			for (byte i = 0; i < (MAX_LEVEL >> 1); i++) {
				if (leaf.get(i) == null)
					sb.append('.');
				else
					sb.append('*');
			}
			sb.append('\n');

			// the second line
			sb.append("    ");
			if (cur.level() > 10) {
				for (int i = cur.level() - 10; i >= 0 && k < 10; i--, k++) {
					sb.append(String.format("%02x|", cur.offset(i)));
				}
			}
			for (; k < 20; k++) {
				sb.append("  |");
			}
			sb.append("  ");
			for (int i = (MAX_LEVEL >> 1); i < MAX_LEVEL; i++) {
				if (leaf.get((byte) i) == null)
					sb.append('.');
				else
					sb.append('*');
			}
			sb.append('\n');
			try {
				w.append(sb.toString());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

	}
}
